﻿// 4335. 博格迷宫.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
https://www.acwing.com/problem/content/4338/


博格迷宫是一个 M
 行 N
 列的方格矩阵。

每个方格要么是无法通过的墙壁（用 # 表示），要么是可以通过的空地（用 表示）。

在迷宫的一些空地中存在着被困人员（用 A 表示）。

为了解救这些被困人员，政府派出了救援队伍。

初始时，救援队伍位于某空地处（用 S 表示）。

救援队伍可以沿上下左右四个方向进行移动，每次移动一格距离。

为了提高救援效率，救援队伍可以选择将队伍进行拆分，分为任意多个小股救援队伍，各自行动，开展救援。

但是，拆分救援队伍并不是无条件的，只有以下两种情况可以进行队伍拆分：

救援最开始时，位于 S 处的最初救援队伍可以选择进行拆分。
当某个救援队伍抵达某个被困人员所在位置时，该救援队伍可以选择进行拆分。
我们规定，整个救援行动的成本定义为参与救援的所有队伍走过的总距离。

例如，如果救援行动的完整过程为：

初始队伍移动 5
 格距离，救到某被困人员，并选择拆分为两只小队。
第 1
 支小队移动 2
 格距离，救到某被困人员，并停止行动。
第 2
 支小队移动 4
 格距离，救到最后一位被困人员，救援结束。
那么，所有队伍走过的总距离为 5+2+4=11
。

请你计算并输出参与救援的所有队伍走过的总距离的最小可能值。

已知，迷宫的周边是封闭的，也就是说救援队伍不可能从 S 处走到迷宫外。

另外，保证所有被困人员的位置都一定可以抵达。

输入格式
第一行包含整数 T
，表示共有 T
 组测试数据。

每组数据第一行包含两个整数 N,M
。

接下来 M
 行，每行包含一个长度为 N
 的字符串，表示整个迷宫。

输出格式
每组数据输出一行答案，一个整数，表示参与救援的所有队伍走过的总距离的最小可能值。

数据范围
1≤T≤50
,
1≤N,M≤50
，
每组数据被困人员不超过 100
 个。

输入样例：
2
6 5
#####
#A#A##
# # A#
#S  ##
#####
7 7
#####
#AAA###
#    A#
# S ###
#     #
#AAA###
#######
输出样例：
8
11
*/
int main()
{
    std::cout << "Hello World!\n";
}

 